//
// Created by EDZ on 2022/1/13.
//

#ifndef INC_2022_1_FUN_H
#define INC_2022_1_FUN_H
#include "../head/common.h"
using namespace std;

/**
 * 最长有效括号
 * @param s
 * @return
 */
int longestValidParentheses(string s){
    stack<int> st;
    int maxLength = 0;
    vector<bool> flag(s.size());
    int currentLength = 0;
    for(int i=0;i<s.size();i++){
        flag[i] = 0;
        if(s[i]=='(')
            st.push(i);
        else{
            if(st.empty()){
                flag[i] = 1;
            }else
                st.pop();
        }
    }
    while(!st.empty()){
        int i = st.top();
        flag[i] = 1;
        st.pop();
    }
    for(auto && i : flag){
        if(i==1){
            maxLength = max(maxLength,currentLength);
            currentLength = 0;
            continue;
        }
        currentLength++;
    }
    maxLength = max(maxLength,currentLength);
    cout<<maxLength<<endl;
    return maxLength;
}

/**
 * 接雨水问题
 * @param height
 * @return
 */
int trap(vector<int>& height) {
    int size = height.size();
    int left[size],right[size];
    int num = 0;
    left[0] = height[0],right[size-1] = height[size-1];
    for(int i=1;i<size;i++){
        left[i] = max(left[i-1],height[i-1]);
        right[size-i-1] = max(right[size-i],height[size-i]);
    }
    for(int i=1;i<size-1;i++){
        num += max(0,min(left[i],right[i]) - height[i]);
    }
    return num;
}

/**
 * 跳一跳
 * @param nums
 * @return
 */
int jump(vector<int>& nums) {
    int step = 0;
    int end = 0;
    int distance = 0;
    for(int i=0;i<nums.size()-1;i++){
        distance = max(distance,i+nums[i]);
        if(i==end){
            end = distance;
            step++;
        }
    }
    cout<<step<<endl;
    return step;
}

int maxChildArraySum(vector<int> &a){
    int n = a.size();
    int b[n];
    b[0] = a[0];
    for(int i=1;i<n;i++){
        b[i] = max(b[i-1]+a[i],a[i]);
    }
    return 0;
}

bool isEqual(char c1, char c2) {
    return c2 == '?' || c1 == c2;
}

bool isMatch(string s, string p) {
    if(s.empty() || p.empty()) {
        return false;
    }
    int m = s.length();
    int n = p.length();
    int i = 0;
    int j = 0;
    int star_idx = -1;
    int match = 0;
    while(i < m) {
        if((j<n) && p[j] != '*' && isEqual(s[i], p[j])) {
            i++;
            j++;
        }
        else if((j<n) && p[j] == '*') {
            star_idx = j;
            match = i;
            j++;
        }
        else if(star_idx != -1) {
            j = star_idx + 1;
            match++;
            i = match;
        }
        else {
            return false;
        }
    }
    while(j<n && p[j] == '*') {
        j++;
    }
    return j == n;
}



bool isMatch_yun(string s, string p) {
    int sl = s.size();
    int pl = p.size();
    int i = 0, j = 0, pMatch = -1, iMatch = 0;
    while (i < sl) {
        if ((p[j] != '*' && s[i] == p[j]) || p[j] == '.' && j < pl) {
            i++;
            j++;
        } else if (p[j] == '*' && j < pl) {
            iMatch = i;
            pMatch = j;
            j++;
        } else if (pMatch != -1) {
            iMatch++;
            i = iMatch;
            j = pMatch + 1;
        } else {
            return false;
        }
        cout << j << endl;
    }
    while (j < pl && p[j] == '*') {
        j++;
    }
    return j == pl && i == sl;
}

/**
 * 最大子数组和
 * @param nums
 * @return
 */
int maxSubArray(vector<int> &nums) {
    //以i结尾的最大数组和
    int size = nums.size();
    int maxVal = nums[0];
    for (int i = 1; i < size; i++) {
        nums[i] = max(nums[i - 1] + nums[i], nums[i]);
        maxVal = max(maxVal, nums[i]);
    }
    return maxVal;

}

/**
 * 跳跃游戏
 * 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
 * @param nums
 * @return
 */
bool canJump(vector<int> &nums) {
    int maxStep = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (i <= maxStep) {
            maxStep = max(i + nums[i], maxStep);
        } else
            break;
    }
    if (maxStep < nums.size() - 1) {
        return false;
    }
    return true;
}

/**
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
 * @param m
 * @param n
 * @return
 */
int uniquePaths(int m, int n) {
    int a[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if ((i == 0) || (j == 0))
                a[i][j] = 1;
            else {
                a[i][j] = a[i - 1][j] + a[i][j - 1];
            }
        }
    }
    return a[m - 1][n - 1];
}

int uniquePaths_yun(int m, int n) {
    int s = 1;
    int j = 1;

    for (int i = n + 1; i <= m + n; i++) {
        s = s * i / j;
        j++;
    }

    return s;
}

/**
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
 * @param obstacleGrid
 * @return
 */
int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) {
    int m = obstacleGrid.size();
    int n = obstacleGrid[0].size();
    int a[m][n];
    if (obstacleGrid[m - 1][n - 1] == 1) {
        return 0;
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if ((i == 0) || (j == 0)) {
                a[i][j] = 1;
                if (i > 0) {
                    a[i][j] = a[i - 1][j];
                }
                if (j > 0) {
                    a[i][j] = a[i][j - 1];
                }
                if (obstacleGrid[i][j] == 1) {
                    a[i][j] = 0;
                }
            } else {
                if (obstacleGrid[i][j - 1] == 1 && obstacleGrid[i - 1][j] != 1) {
                    a[i][j] = a[i - 1][j];
                } else if (obstacleGrid[i - 1][j] == 1 && obstacleGrid[i][j - 1] != 1) {
                    a[i][j] = a[i][j - 1];
                } else if ((obstacleGrid[i][j - 1] == 1 && obstacleGrid[i - 1][j] == 1) || obstacleGrid[i][j] == 1) {
                    a[i][j] = 0;
                } else {
                    a[i][j] = a[i - 1][j] + a[i][j - 1];
                }
            }
            cout << a[i][j] << " ";
        }
        cout << endl;
    }

    return a[m - 1][n - 1];
}

/**
 * 假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
2.如果不能获取到任何利润，请返回0
3.假设买入卖出均无手续费
 * @param prices
 * @return
 */
int maxProfit(vector<int> &prices) {
    int curMin = prices[0];
    int maxProfit = 0;
    for (int i = 1; i < prices.size(); i++) {
        curMin = min(curMin, prices[i - 1]);
        maxProfit = max(prices[i] - curMin, maxProfit);
    }
    return maxProfit;
}


/**
 * 两个字符串的最长公共子串
 * @param a
 * @param b
 * @return
 */
pair<int, string> longString(string a, string b) {
    int row = a.size() + 1;
    int line = b.size() + 1;
    int arr[row][line];
    int maxLength = 0;
    int li, lj;
    for (int i = 0; i < a.size() + 1; i++) {
        for (int j = 0; j < b.size() + 1; j++) {
            if (i == 0 || j == 0) {
                arr[i][j] = 0;
            } else if (a[i - 1] == b[j - 1]) {
                arr[i][j] = arr[i - 1][j - 1] + 1;
            } else {
                /*连续子串*/
                arr[i][j] = 0;

                /*不连续的子序列*/
                //arr[i][j] = max(arr[i-1][j],arr[i][j-1]);
            }
            if (arr[i][j] > maxLength) {
                li = i;
                lj = j;
            }
            maxLength = max(maxLength, arr[i][j]);
        }
    }
    string s = "";
    int i = a.size() - 1;
    int j = b.size() - 1;
    while (i >= 0 && j >= 0) {
        if (a[i] == b[j]) {
            s = s + a[i];
            i--;
            j--;
        } else {
            if (arr[i][j] == arr[i - 1][j]) {
                j--;
            } else {
                i--;
            }
        }
    }
    pair<int, string> pair;
    pair.first = maxLength;
    reverse(s.begin(), s.end());
    pair.second = s;
    return pair;
}


/**
 * 对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。
 * @param A
 * @return
 */
int getLongestPalindrome(string A) {
    int l = A.size();
    int arr[l][l];
    int maxLength = 0;
    for (int p = 0; p < l; p++) {
        for (int q = 0; p + q < l; q++) {

            /*
             * 判断从下表q到p+q是否是回文串
             */
            arr[q][p + q] = 0;
            if (p == 0) {
                arr[q][p + q] = 1;
            } else if (p == 1) {
                if (A[q] == A[q + p]) {
                    arr[q][p + q] = 1;
                }
            } else if (p > 1) {
                if (A[q] == A[p + q] && arr[q + 1][p + q - 1]) {
                    arr[q][p + q] = 1;
                }
            }
            if (arr[q][p + q] == 1)
                maxLength = max(p, maxLength);
        }
        cout << endl;

    }
    return maxLength + 1;
}

int minEditCost(string str1, string str2, int ic, int dc, int rc) {
    // write code here
    int len1 = str1.size();
    int len2 = str2.size();
    int dp[len1 + 1][len2 + 1];
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= len1; i++) dp[i][0] = i * dc;  // str2 长度为0，只能删除
    for (int i = 1; i <= len2; i++) dp[0][i] = i * ic; // str1 长度为0， 只能插入
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (str1[i - 1] == str2[j - 1]) dp[i][j] = dp[i - 1][j - 1];  //r1[i] = str2[j]
            else {
                dp[i][j] = min(dp[i - 1][j - 1] + rc, dp[i][j - 1] + ic);   //dp[i][j] 取三种措施的最小的代价
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + dc);
            }
        }
    }
    return dp[len1][len2];
}

/**
 * 以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。
 * @param s
 * @param t
 * @return
 */
string solveAdd(string s, string t) {
    string r = "";
    int i = s.size() - 1, j = t.size() - 1, k = 0;
    int up = 0;
    while (i >= 0 || j >= 0) {

        int a, b;
        if (i < 0)
            a = '0';
        else
            a = s[i];
        if (j < 0)
            b = '0';
        else
            b = t[j];
        int val = (a + b + up - '0' * 2);
        r +=  val%10 + '0';
        cout<<&r<<endl;
        up = val/10;
        i--, j--;
    }
    if(up>0)
        r += up+'0';
    reverse(r.begin(), r.end());
    cout << r << endl;
    return r;
}

/**
 * 以字符串的形式读入两个数字，编写一个函数计算它们的乘积，以字符串形式返回。
 * @param s
 * @param t
 * @return
 */
string solveMul(string s, string t) {
    int r[s.size()+t.size()+1];
    char result[s.size()+t.size()+1];
    memset(r,0,(s.size()+t.size()+1)*sizeof(int));
    memset(result,'0',(s.size()+t.size()+1)*sizeof(char ));
    for(int i = s.size()-1;i>=0;i--){
        for(int j = t.size()-1;j>=0;j--){
            r[i+j+2] += (s[i]-'0')*(t[j]-'0');
        }
    }
    for(int i=s.size()+t.size();i>0;i--){
        int up = 0;
        if(r[i]>9){
            up = r[i]/10;
            r[i] = r[i]%10;
            r[i-1] += up;
        }
        result[i] = r[i]+'0';
    }
    for(int i=0;i<s.size()+t.size()+1;i++){
        if(result[i]!='0')
        {
            string m(result+i,s.size()+t.size()+1-i);
            return m;
        }
    }
    return string(result,1);

}

/**
 * https://leetcode-cn.com/problems/roman-to-integer/
 * @param s
 * @return
 */
int romanToInt(string s) {
    map<char,int> dic = {{'I',1},{'V',5},{'X',10},
                           {'L',50},{'C',100},{'D',500},{'M',1000}};
    int sum = 0;
    int l = s.size();
    for(int i = 0;i<l;i++){
        if(s[i]=='I'&&(s[i+1]=='V'||s[i+1]=='X') || s[i]=='X'&&(s[i+1]=='L'||s[i+1]=='C') || s[i]=='C'&&(s[i+1]=='D'||s[i+1]=='M')){
            sum -= dic.find(s[i])->second;
        }else
            sum+=dic.find(s[i])->second;

    }
    return sum;

}

/**
 * https://leetcode-cn.com/problems/longest-common-prefix/
 * @param strs
 * @return
 */
string longestCommonPrefix(vector<string>& strs) {
    int l = strs.size();
    int n = strs[0].size();
    for(int i = 0;i<n;i++){
        char f = strs[0][i];
        for(int j = 0;j<l;j++){
            if(strs[j].size()<i)
                return strs[j];
            if(strs[j][i]!=f)
                return strs[j].substr(0,i);
        }
    }
    return strs[0];
}
#endif //INC_2022_1_FUN_H
